package com.mc.algorithm;

import java.util.ArrayList;
public class Solution {
    public ArrayList<String> fin = new ArrayList<String>();
    public StringBuilder sb = new StringBuilder();
    
    public ArrayList<String> Permutation(String str) {
    	if(str==null)
            return null;
        if(str.length()==0)
            return fin;
        char[] cha = str.toCharArray();
        int[] flag = new int[cha.length];
        recurse(0,flag,cha);
        return fin;
    }
    public void recurse(int num,int[] flag,char[] ch){
        if(num==ch.length){
            if(!fin.contains(sb.toString()))
            	fin.add(sb.toString());
            return;
        }
        for(int i=0;i<ch.length;i++){
            if(flag[i]==0){
                flag[i]=1;
                sb.append(ch[i]);
                recurse(num+1,flag,ch);
                sb.deleteCharAt(sb.length()-1);
                flag[i]=0;
            }
        }
    }
    public static void main(String[] args) {
		Solution s = new Solution();
		ArrayList<String> t = s.Permutation("adhjks");
		for(int i=0;i<t.size();i++)
			System.out.println(t.get(i));
    }
}